Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
56 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, ...
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 ...
4 votes
1 answer
371 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$ ...
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 ...
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 ...
1 vote
2 answers
386 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 \...
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 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 ...
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 ...
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|\...
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 ...
3 votes
1 answer
154 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 ...
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 ...
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 ...
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 ...
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., ...
1 vote
1 answer
90 views

How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?

I have a $k$-partite $k$-uniform hypergraph $H$ with $V(H) = V_1 \cup\cdots\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. ...
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 $...
2 votes
1 answer
298 views

Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
1 vote
0 answers
63 views

Lower bound for the minimum of the maximum frequency of an element - with restrictions

Consider a family $\mathcal{F}$ of non-empty sets, with $n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$. It is known that of the $\binom{n}{2}$ ways ...
6 votes
1 answer
232 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 ...
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 ...
2 votes
1 answer
160 views

Bounds for $\mathrm{ex}(n,K_{2,\dots,2}^{(r)})$

$\DeclareMathOperator\ex{ex}$We write $K_{2,\dots,2}^{(r)}$ to denote the $r$-uniform hypergraph with vertex set $\{1,2\}\times\{1,\dots,r\}$ and hyperedge set $\{(1,1),(1,2)\}\times \{(2,1),(2,2)\} \...
6 votes
2 answers
392 views

Coloring of a graph representing the power set

For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S_1,S_2 \in \mathcal{P}$, the edge $(S_1,S_2)$ exists ...
23 votes
3 answers
3k views

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality? Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
4 votes
3 answers
780 views

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
3 votes
2 answers
275 views

Ramsey-Turán density function is well defined

Define $$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$ and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as $$f_l(\alpha)=\lim_{n\to \infty}...
4 votes
1 answer
886 views

Existence of triangle-free graphs for regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
3 votes
0 answers
70 views

Boundary differences in two graphs

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
4 votes
0 answers
104 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
7 votes
1 answer
513 views

A proper definition of connectivity for hypergraphs

For usual graphs on $n$ vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has $n-1$ edges. I would like to know whether ...
2 votes
0 answers
190 views

The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
21 votes
0 answers
441 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
3 votes
1 answer
121 views

The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles

Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles. Clearly, $c(n, 1) = 1$ and it not very hard to ...
1 vote
2 answers
205 views

Extremal density of a graph without a non-backtracking $2k$-cycle

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form $$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$ while the ...
3 votes
0 answers
66 views

An extremal problem in directed path systems

The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$: What is the asymptotically maximum $L = L(n)$ such that ...
3 votes
1 answer
288 views

Graph properties that imply a bounded number of edges

Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...
4 votes
1 answer
220 views

Maximal number of perfect matchings that pairwise form a Hamiltonian cycle

Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle. Question: Is it true that $MH(...
1 vote
2 answers
360 views

Tight bound of Turan number for K_{1,t,t}

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t. The motivation is that we now $ex_2(n,K_{t,t})=O(...
0 votes
1 answer
1k views

Vertex cover of regular graph

(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...
2 votes
1 answer
354 views

Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...
6 votes
2 answers
349 views

extremal bipartite graph

I'm facing the following question: Given a bipartite graph $G = (L \cup R, E)$. Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$. What is a minimal possible number of ...
6 votes
1 answer
612 views

Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...
5 votes
0 answers
226 views

Diameter of subset sum graph

We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$. Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...