Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $G = {\mathbb{F}}_2^n$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.
more »
« less
Concatenating Bipartite Graphs
Let $x,y\in (0,1]$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbours in $B$, and every vertex in $B$ has at least $y|C|$ neighbours in $C$, and there are no edges between $A,C$. We denote by $\phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v\in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. This function has some interesting properties: we show, for instance, that $\phi(x,y)=\phi(y,x)$ for all $x,y$, and there is a discontinuity in $\phi(x,x)$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $\phi(x,y)\ge z$ and the pairs with $\phi(x,y)1/3$.
more »
« less
- NSF-PAR ID:
- 10333176
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 29
- Issue:
- 2
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $ \Sigma $ of genus $ g$ and let $ L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $ \phi $ with domain $ V(G)$ such that $ \phi (v)\in L(v)$ for every $ v\in V(G)$ and $ \phi (v)\ne \phi (u)$ for every pair of adjacent vertices $ u,v\in V(G)$. We prove if every non-null-homotopic cycle in $ G$ has length $ \Omega (\log g)$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $ \vert V(G)\vert=O(g)$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and a set $ X\subseteq V(G)$ of vertices that are pairwise at distance $ \Omega (1)$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $ \Omega (1)$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $ 2^{\Omega (\vert V(G)\vert)}$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.more » « less
-
null (Ed.)Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.more » « less
-
Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c∈N such that for every graph G∈C there is a collection P of partitions (X,Y) of the vertex set of G with |P|≤|V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K∩S=∅, then there is (X,Y)∈P with K⊆X and S⊆Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S,K of graphs and show that for every S∈S and K∈K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.more » « less
-
more » « less
Abstract For a subgraph
$G$ $F$ $\delta ^*(G)$ $G$ $F$ $G$ $C_3$ $n$ $\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$ $G$ $n$ $G$ $C_k$ $n$ $\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$ $G$ $n$ $C_k$ $C_k$ $k$ $k=3$ $n$ In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of
$G$
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/8451
