All Questions
Tagged with extremal-graph-theory co.combinatorics
162 questions
1
vote
0
answers
132
views
Specific regularity in bipartite graphs
Let $G(A,B)$ be a bipartite graph with $|A| = |B| = n$, where $n$ is sufficiently large(thus, $o(n)/n,o(n^2)/n^2\ll 1$). The edge density of $G$ is $d = \frac{e(A,B)}{n^2}$, where $e(A,B)$ denotes the ...
- 359
0
votes
0
answers
57
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 359
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 359
4
votes
1
answer
376
views
Looking for a counterexample to a strengthening of the union-closed sets conjecture
[Now crossposted at math.stackexchange]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ ...
- 700
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 359
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 359
1
vote
2
answers
391
views
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 700
0
votes
0
answers
68
views
Proving we can minimize the number of crossings by having a planar embedding of $K_{2,2}$ encircle another out of any 2 such embeddings
Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $...
- 1
2
votes
0
answers
48
views
On planar graphs with specific spanning tree count and poly number of vertices
Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.9k
1
vote
0
answers
63
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 359
1
vote
1
answer
141
views
Covering a bounded degree graph with subgraphs of bounded sizes
Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta \ge 2$. Let $\mathcal G = \{G_1,G_2,\ldots\}$ be a collection of subgraphs of $G$ such that every edge of $G$ is contained in ...
- 277
0
votes
0
answers
43
views
Locally uniformly convexity in kernels (generalized definition of graphon) with cut norm
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 359
0
votes
0
answers
52
views
Does "epsilon-regular" equal to "cut distance less than epsilon"?
Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?
$G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
- 359
0
votes
0
answers
49
views
Property of edge-vertex transitive graphs
Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
- 359
3
votes
1
answer
155
views
Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?
Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...
- 359
0
votes
0
answers
39
views
Does this "linear-approximated" version of Graph Counting Lemma hold?
Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
- 359
4
votes
1
answer
357
views
A question related to "Locally Sidorenko" type problem
Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
- 359
3
votes
1
answer
81
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
1
vote
0
answers
107
views
Turán number of even cycles with diagonal
Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle.
What is known about the Turán ...
- 19.1k
2
votes
0
answers
61
views
Some version of graph removal lemma
I found the following statement in 'A proof of the stability of extremal graphs,
Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi:
Lemma: For any $\alpha>0$ and a graph $F$, ...
- 281
1
vote
1
answer
75
views
Lower bound for the sum of the number of vertices of some subgraphs of a directed graph
Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.
Let $C(V_i)$ be the union of ...
- 700
1
vote
2
answers
75
views
The edit distance from a large complete $p$-partite graph to the Turán graph
Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turán graph.
Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
- 113
4
votes
1
answer
136
views
Longest paths and cycles in Steiner triple systems
A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists
of $2t$ cyclically ...
- 373
4
votes
0
answers
113
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
- 557
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
2
votes
1
answer
175
views
Clique number of $k$-critical graphs
A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$， where $\chi(G)$ denotes the chromatic number of $G$. The ...
- 51
2
votes
1
answer
131
views
Turán density of hypergraphs with very few edges
As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
- 19.1k
4
votes
1
answer
111
views
Are there decompositions of $K_{16}$ by certain 3-regular graphs?
This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:
Can the (edges ...
- 13.4k
2
votes
2
answers
143
views
Regarding a specific Turán number of graphs
I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...
- 2,089
4
votes
0
answers
241
views
Weight transfer proof of Turán’s theorem
Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...
1
vote
1
answer
125
views
Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$
I know that it must be a simple consequence of the Kővári–Sós–Turán (and Erdős–Stone) theorem, but I am struggling to formulate a proof: Let $H$ be a fixed-size $r$-chromatic graph. Then there exists $...
5
votes
1
answer
225
views
Cover a graph with small size complete graphs
Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...
- 53
0
votes
0
answers
55
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
- 199
3
votes
0
answers
330
views
Behrend's construction vs. Triangle removal lemma
I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand.
Theorem 2.3.1 (Triangle removal lemma) For all $\...
- 330
6
votes
1
answer
234
views
Graphs without short cycles and with linear number of edges
Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...
- 655
4
votes
1
answer
465
views
Turán's theorem for cosets of groups
Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
- 1,462
11
votes
0
answers
195
views
Number of triangle-free graphs with prescribed number of edges
This question is posted from StackExchange since it received no answer there.
Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
- 384
1
vote
0
answers
74
views
Graph removal lemma
The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...
- 373
2
votes
0
answers
54
views
A variant of the regularity lemma that depends on the number of vertices
Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side.
For sets $X \subseteq U$ and $Y \subseteq V$,
let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
- 419
4
votes
1
answer
137
views
On the number of disjoint subsets of a large set families
Let $[n] := \{1,\dots,n\}$, for some large integer $n$, and let $\mathcal{F}$ be a family of 2-element subsets of $[n]$.
The famous Erdös-Ko-Rado (EKR) theorem says that if $|\mathcal{F}| > {n - 1 ...
- 43
0
votes
0
answers
148
views
Szemeredi's regularity lemma for countably infinite graphs?
Consider the following version of Szemeredi's regularity lemma found in the Fox and Lovasz paper, "A tight lower bound for Szemeredi's regularity lemma", arXiv: 1403.1768v1 [math.CO] 7 Mar ...
- 6,132
6
votes
5
answers
540
views
Existence of connected set with large edge boundary
Let $\Gamma=(V,E)$ be a finite connected graph.
Pretty standard notation. Given a set $S\subset V$, write $\Gamma|_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\...
- 20.2k
4
votes
2
answers
269
views
Intuition on inequality in proving a bound on the sum of squares of degrees of a graph
Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality
$$\...
- 662
4
votes
1
answer
366
views
The upper bound of edges of the generalized cactus graphs
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple ...
- 1,851
5
votes
0
answers
156
views
$K_4$ or n vertices without triangles
For which minimal $m(n)$ any graph on $m$ vertices contains either a complete subgraph on 4 vertices $K_4$ or $n$-vertices subgraph without triangles? I know a quadratic upper bound $2n^2$, but I am ...
- 115
1
vote
0
answers
79
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
- 135
7
votes
0
answers
152
views
Inequality of product of discrete cosines
Let $k,a,b,c$ be odd positive integers. Consider the following inequality:
$$
\sum_{x,y \in [k]} \cos^a\bigg(\frac{2\pi}{k}\cdot x\bigg) \cdot \cos^b\bigg(\frac{2\pi}{k}\cdot y\bigg) \cdot \cos^c\bigg(...
- 71
4
votes
1
answer
195
views
Explicit constructions of regular graphs with very sparse induced subgraphs
Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
2
votes
1
answer
210
views
3-uniform tetrahedron-free hypergraph on seven vertices
My problem concerns 3-uniform hypergraphs. Let $f(n)$ be the maximal number of edges in a 3-uniform hypergraph such that no four edges form a "tetrahedron", i.e., four edges that join the ...
- 2,811