An official website of the United States government
Abstract A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $$r\in (1,2)$$ there exists a bipartite graph H such that $$\mathrm{ex}(n,H)=\Theta(n^r)$$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $$k\geq 2$$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $$k\geq 2$$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $$^{\prime}$$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $$^{\prime}$$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $$^{\prime}$$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ .
more »
« less
Optimal point sets determining few distinct angles
Let P(k) denote the largest size of a non-collinear point set in the plane admitting at most k distinct angles. We prove P(2) = P(3) = 5, and we characterize the optimal sets. We also leverage results from Fleischmann et al. [Disc. Comput. Geom. (2023)] to provide the general bounds k+2 ≤ P(k) ≤ 6k, although the upper bound may be improved pending progress toward the Strong Dirac Conjecture. We conjecture that the lower bound is tight, providing infinite families of configurations meeting the bound and ruling out several classes of potential counterexamples.
more »
« less
- PAR ID:
- 10498058
- Publisher / Repository:
- AUSTRALASIAN JOURNAL OF COMBINATORICS
- Date Published:
- Journal Name:
- AUSTRALASIAN JOURNAL OF COMBINATORICS
- Volume:
- 87
- Issue:
- 1
- ISSN:
- 2202-3518
- Page Range / eLocation ID:
- 2023
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A conjecture of Kalai asserts that for $$d\geq 4$$, the affine type of a prime simplicial $$d$$-polytope $$P$$ can be reconstructed from the space of affine $$2$$-stresses of $$P$$. We prove this conjecture for all $$d\geq 5$$. We also prove the following generalization: for all pairs $(i,d)$ with $$2\leq i\leq \lceil \frac d 2\rceil -1$$, the affine type of a simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-i+1$$ can be reconstructed from the space of affine $$i$$-stresses of $$P$$. A consequence of our proofs is a strengthening of the Generalized Lower Bound Theorem: it was proved by Nagel that for any simplicial $(d-1)$-sphere $$\Delta $$ and $$1\leq k\leq \lceil \frac {d}{2}\rceil -1$$, $$g_{k}(\Delta )$$ is at least as large as the number of missing $(d-k)$-faces of $$\Delta $$; here we show that, for $$1\leq k\leq \lfloor \frac {d}{2}\rfloor -1$$, equality holds if and only if $$\Delta $$ is $$k$$-stacked. Finally, we show that for $$d\geq 4$$, any simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-1$$ is redundantly rigid, that is, for each edge $$e$$ of $$P$$, there exists an affine $$2$$-stress on $$P$$ with a non-zero value on $$e$$.more » « less
-
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝ d that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2 –polylog( d ) ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank- d matrix containing at most O (1) distinct entries in each column contains a submatrix of fractional size 2 –polylog( d ) , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k -partitions to bounds for parallel ( k -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2 d / d ) in any d -dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [ 2 ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2 -Ω (√ d ) , and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank( f )) bound [ 20 ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations.more » « less
-
Abstract Given a $$k$$-uniform hypergraph $$H$$ on $$n$$ vertices, an even cover in $$H$$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $$2$$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $$k$$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial [3], Feige conjectured [8] an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $$k$$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges [12, 13]. These works introduce the new technique that relates hypergraph even covers to cycles in the associated Kikuchi graphs. Their analysis of these Kikuchi graphs, especially for odd $$k$$, is rather involved and relies on matrix concentration inequalities. In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige’s conjecture for even $$k$$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $$k$$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds [4] on 3-query binary linear locally decodable codes.more » « less
-
If a knot K in S^3 admits a pair of truly cosmetic surgeries, we show that the surgery slopes are either ±2 or ±1/q for some value of q that is explicitly determined by the knot Floer homology of K. Moreover, in the former case the genus of K must be 2, and in the latter case there is a bound relating q to the genus and the Heegaard Floer thickness of K. As a consequence, we show that the cosmetic crossing conjecture holds for alternating knots (or more generally, Heegaard Floer thin knots) with genus not equal to 2. We also show that the conjecture holds for any knot K for which each prime summand of K has at most 16 crossings; our techniques rule out cosmetic surgeries in this setting except for slopes ±1 and ±2 on a small number of knots, and these remaining examples can be checked by comparing hyperbolic invariants. These results make use of the surgery formula for Heegaard Floer homology, which has already proved to be a powerful tool for obstructing cosmetic surgeries; we get stronger obstructions than previously known by considering the full graded theory. We make use of a new graphical interpretation of knot Floer homology and the surgery formula in terms of immersed curves, which makes the grading information we need easier to access.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
