Noam Lifshitz, Product free sets in the alternating group
A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product …
10 events found.
Virtual Discrete Math Colloquium
Events
-
-
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
-
-
Lars Jaffke, Taming graphs with no large creatures and skinny ladders
Zoom ID: 869 4632 6610 (ibsdimag)We confirm a conjecture of Gartland and Lokshtanov : if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature …
-
Akash Kumar, Random walks and Forbidden Minors
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how …
-
Brett Leroux, Expansion of random 0/1 polytopes
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives …
-
Raphael Steiner, Congruence-constrained subdivisions in digraphs
Zoom ID: 869 4632 6610 (ibsdimag)I will present the short proof from that for every digraph F and every assignment of pairs of integers $(r_e,q_e)_{e\in A(F)}$ to its arcs, there exists an integer $N$ such …
-
-
Dömötör Pálvölgyi, C-P3O: Orientation of convex sets and other good covers
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other …
-
Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey …
-
Santiago Guzmán-Pro, Local expressions of graphs classes
Zoom ID: 869 4632 6610 (ibsdimag)A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes, the set of minimal obstructions might be infinite, or too complicated to describe. For instance, for any …
-
-
Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]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 …
-
-
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. …