For a fixed graph H, consider the graph homomorphism problem Hom(H), i.e. find an edge-preserving mapping from V(G) to V(H). Specifically, if H is the complete graph K_k, Hom(H) is equivalent to k-Coloring. Thus, even in this special case the problem is NP-complete for each k ≥ 3, and it is also NP-complete for nearly all other graphs H.

Okrasa и Rzaͅżewski [SODA 2020] showed the following dichotomy for Hom(H) with respect to treewidth of G: Hom(H) can be solved in time |H|^tw(G) poly(|V(G)|), but for any ε > 0 there is no algorithm for Hom(H) with running time (|H| - ε)^tw(G) poly(|V(G)|), assuming SETH.
As stated, the result holds only if H is a projective core, however a similar dichotome follows for nearly all graphs. Moreover, assuming a long-standing hypothesis from algebraic graph theory, this classsification covers all graphs H.

In this talk, we show a similar dichotomy with respect to cliquewidth of G. Cliquewidth, similarly to treewidth, is a structural width parameter of the graph, albeit a more general one: cliquewidth is always bounded when treewidth is bounded, but also for other dense graph classes, e.g. cliques. The conditions under which the dichotomy is given repear the conditions obtained for treewidth, however the preciese running time bound is f(H)^cw(G) poly(|V(G)|), where cw(G) is the cliquewidth of G, and f(H) is a certain structural parameter of H, specifically the number of distinct open neighborhoods of subsets of V(H).

This is a joint work with Robert Ganian, Thekla Hamm, Viktoria Korchemna and Karolina Okrasa.

Дистанционно регулярные антиподальные накрытия полных графов образуют обширный класс графов, который тесно связан со многими важными алгебраическими или комбинаторными объектами, такими как обобщенные матрицы Адамара, проективные плоскости, обобщенные четырехугольники, делимые дизайны и коды. Кроме того, такие накрытия оказываются источником некоторых специальных множеств равноугольных прямых (ETFs, SIC-POVMs), применяемых в дискретной геометрии и квантовой теории информации. Несмотря на то, что полное их описание представляется недостижимым, можно надеяться на получение новых их конструкций и частичную классификацию при дополнительных ограничениях групповой природы.

Доклад посвящен исследованию реберно-транзитивных дистанционно регулярных антиподальных накрытий полных графов. Пусть $\Gamma$ --- это такое накрытие и $G$ --- это его полная группа автоморфизмов. Обозначим через $\Omega$ и $\mathcal{S}$ множество вершин накрытия $\Gamma$ и множество орбиталов группы $G$ на $\Omega$ соответственно. Тогда пара ${\rm Inv}(G)=(\Omega,\mathcal{S})$ образует шурову схему отношений, ассоциированную с группой $G$.
При этом множество дуг накрытия является объединением набора из не более двух орбиталов группы $G$ и кроме того, $G$ индуцирует $2$-однородную группу подстановок $G^{\Sigma}$ на множестве $\Sigma$ антиподальных классов накрытия $\Gamma$, которая ввиду теорем Кантора и Бернсайда является либо почти простой, либо аффинной. В данном докладе будут представлены результаты автора по классификации накрытий $\Gamma$, полученные в обоих указанных случаях для $G^{\Sigma}$, а также по их характеризации как графов базисных отношений схем ${\rm Inv}(G)$ в случае, когда $G^{\Sigma}$ --- почти простая группа.

We introduce the following variant of the VC-dimension. Given S ⊆ {0, 1} and a positive integer d, we define U_d(S) to be the size of the largest subset I ⊆ [n] such that the projection of S on every subset of I of size d is the d-dimensional cube. We show that determining the largest cardinality of a set with a given Ud dimension is equivalent to a Turán-type problem related to the total number of cliques in a d-uniform hypergraph. This allows us to beat the Sauer-Shelah lemma for this notion of dimension. We use this to obtain several results on Σ_3^k-circuits, i.e., depth-3 circuits with top gate OR and bottom fan-in at most k:

* Tight relationship between the number of satisfying assignments of a 2-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. ’00).

* Improved Σ_3^3 -circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement.

This is a joint work with Peter Frankl and Navid Talebanfard.