2
$\begingroup$

Are there explicit constructions of graph families with the following property:

$G_n$ is the graph on $n$ vertices in the family, $\omega(G_n)$ is the size of the biggest clique in the graph $G_n$, $\alpha(G_n)$ is the size of the biggest independent set in $G_n$, then we have

$$\omega(G_n)\alpha(G_n) \leq tn$$

for some $t$ where $t<0.8$.

Observe that,

$t=1$ can be trivially achieved by taking the family with $K_n$ (complete graph on $n$ vertices).

$t=0.8$ can be achieved by taking the family where $G_{5i}$ is the graph with $i$ copies of $C_5$.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ paley graph ${}{}{}$ $\endgroup$
    – mathworker21
    Commented Dec 24, 2022 at 17:07
  • 3
    $\begingroup$ I guess either $\alpha(G)$ or $\omega(G)$ (but not both) is to be the size of the biggest coclique, not clique as written. $$ $$ In general, for any explicit graph $G$ on $n$ vertices that attains $\alpha \omega = tn$ we can use the graphs $k\cdot G$ to attain the same value of $t$. For example, the Paley graph with $n=17$ has $\alpha = \omega = 3$, giving $t = 9/17 < 0.53$. [NB the pentagon $C_5$ is also a Paley graph.] Wikipedia's entry on Ramsey's theorem reports that $R(10,10) \geq 798$; if that's from an explicit construction then we get $t = 81/797 < 0.102$. $\endgroup$
    – Noam D. Elkies
    Commented Dec 24, 2022 at 17:31
  • 3
    $\begingroup$ Unless you really care about very small $n$, I believe what you're looking for are explicit constructions of near-Ramsey graphs. In the computer science literature, this is done via constructions of "two-source extractors"; the state of the art are graphs of size $N=2^n$ for $n$ large enough that contain no clique or independent set of size more than $\log(N)^{o(\log\log\log N)}$. $\endgroup$
    – Jason Gaitonde
    Commented Dec 24, 2022 at 20:00
  • 1
    $\begingroup$ @Agile_Eagle this is a bit old, but you may be interested to know that there are now apparently explicit constructions of graphs with no clique or independent set of size more than $\log^{C}(n)$ for an absolute constant $C\geq 1$ thanks to a very recent breakthrough of Li: eccc.weizmann.ac.il/report/2023/023. This is optimal up to the value of $C$ by classical bounds. $\endgroup$
    – Jason Gaitonde
    Commented Mar 17, 2023 at 2:58

1 Answer 1

Reset to default
4
$\begingroup$

Clearly $\alpha$ and $\omega$ must be at least $2$. There are known explicit families of graphs $G$ for which $\omega = 2$ (so $G$ is triangle-free) and $\alpha \ll n^\theta$ for some $\theta < 1$, so $t \ll n^{\theta-1} \to 0$. Erdos (1966) attained this with $\theta = (3/2) \log_2 (3/2) < 0.88$; according to https://mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/R4n.html the current record is $2/3 < 0.67$, by Alon (1994), whose paper https://www.cs.tau.ac.il/~nogaa/PDFS/r3k1.pdf also cites the 1966 paper by Erdos and a few later improvements. Alon constructs his graphs on pages 2-3, proves the triangle-free property in a paragraph on page 3, and gives the upper bound on $\omega$ in two further pages (proof of Theorem 2.1).

The optimal bound on $\theta$ is $1/2 + o(1)$, but this has yet to be attained by explicit graphs. In the comments Jason Gaitonde reports that there are explicit "two-source extractors" that yield large graphs with $t \ll n^{\epsilon-1}$ for all $\epsilon > 0$, but with both $\alpha \to \infty$ and $\omega \to \infty$; I think that this must be much more recent work.

References

N. Alon: Explicit Ramsey graphs and orthonormal labelings, Electronic J. Combinatorics 1 (1994), R12.

P. Erdos: On the construction of certain graphs, J. Combinatorial Theory 17 (1966), 149--153.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Yes, this is much more recent (see e.g. Barak, et al, Ann. of Math. 2012). A $(n,k)$ 2-source disperser is a function $f:(\{0,1\}^n)^2\to \{0,1\}$ such that for any $A,B\subseteq \{0,1\}^n$ of size $2^k$, $f$ is not constant on $A\times B$. $f$ encodes a bipartite graph on $2^{n+1}$ vertices with no complete or empty bipartite subgraph graph with $2^k$ vertices on each side. This can be converted to a nonbipartite graph on $2^n$ vertices with no clique or independent set of size $2^{k-1}$. The best explicit constructions I know [Li, CCC 2019] give $k=O(\log(n)\log\log(n)/\log\log\log(n))$. $\endgroup$
    – Jason Gaitonde
    Commented Dec 25, 2022 at 2:11
  • $\begingroup$ @JasonGaitonde Thanks, that is what I was looking for $\endgroup$
    – Agile_Eagle
    Commented Dec 25, 2022 at 14:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .