Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube
A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that …
10 events found.
Virtual Discrete Math Colloquium
Events
-
-
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
-
-
Hugo Jacob, On the parameterized complexity of computing tree-partitions
Zoom ID: 869 4632 6610 (ibsdimag)Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. …
-
Chong Shangguan (上官冲), On the sparse hypergraph problem of Brown, Erdős and Sós
Zoom ID: 224 221 2686 (ibsecopro)For fixed integers $r\ge 3, e\ge 3$, and $v\ge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ …
-
-
Cosmin Pohoata, Convex polytopes from fewer points
Zoom ID: 224 221 2686 (ibsecopro)Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position, there exist $n$ points in convex position is one of the most …
-
Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles
Zoom ID: 224 221 2686 (ibsecopro)Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded …
-
-
Pedro Montealegre, A Meta-Theorem for Distributed Certification
Zoom ID: 869 4632 6610 (ibsdimag)Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate …
-
Jan Hladký, Invitation to graphons
Zoom ID: 224 221 2686 (ibsecopro)The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very …
-
-
Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
Zoom ID: 869 4632 6610 (ibsdimag)We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches …
-
Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings
Zoom ID: 869 4632 6610 (ibsdimag)A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large …
-
Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon
Zoom ID: 224 221 2686 (ibsecopro)Let $G=\mathbb{F}_p^n$. Which systems of linear equations $\Psi$ have the property that amongst all subsets of $G$ of fixed density, random subsets minimise the number of solutions to $\Psi$? This …