Yuval Filmus

activity

20102026

most citedOrthogonal basis for functions over a slice of the Boolean hypercube

39 citations · 180 across the 62 of their papers we have counts for

collaborators

Showing math.COShow all

31 papers · 1 filter

math.CO2026

Chvátal's conjecture: a proof from The Book

David Ellis, Yuval Filmus, Ehud Friedgut

Chvátal conjectured that every downset has a maximum-size intersecting family which is a star, that is, consists of all members of the downset containing a fixed element. Recently,…

math.CO2026

Triviality of promise polymorphisms

Yuval Filmus

Given two $m$ -ary predicates $P, Q$ , an $n$ -ary polymorphism is a tuple $(f_{1}, \dots, f_{m})$ of functions such that $x^{(1)}, \dots, x^{(n)} \in P$ implies $(f_1(y_1),\dots,f_m(y_m)) \in…

math.CO2026

Boolean degree one functions on the Grassmann scheme

Yuval Filmus

Ferdinand Ihringer proved that Boolean degree one functions on the Grassmann scheme $J_{q} (n, k)$ are trivial when $min (k, n - k) \geq 2$ and $n$ is large enough. We provide a mostly sel…

math.CO2025

Approximate polymorphisms of predicates

Yaroslav Alekseev, Yuval Filmus

A generalized polymorphism of a predicate $P \subseteq {0, 1}^{m}$ is a tuple of functions $f_{1}, \dots, f_{m} : {0, 1}^{n} \to {0, 1}$ satisfying the following property: If $x^{(1)}…

math.CO2025

Sensitivity and Hamming graphs

Sara Asensio, Yuval Filmus, Ignacio García-Marco +1

For any $m \geq 3$ we show that the Hamming graph $H (n, m)$ admits an imbalanced partition into $m$ sets, each inducing a subgraph of low maximum degree. This improves previous resul…

math.CO2025

Aggregation of evaluations without unanimity

Yuval Filmus

Dokow and Holzman determined which predicates over ${0, 1}$ satisfy an analog of Arrow's theorem: all unanimous aggregators are dictatorial. Szegedy and Xu, extending earlier wor…

math.CO2025

Effective MC-finiteness

Yuval Filmus, Eldar Fischer, Johann A. Makowsky

An integer sequence $(a_{n})_{n \in N}$ is \emph{MC-finite} if for all $m$ , the sequence $a_{n} mod m$ is eventually periodic. There are MC-finite sequences $(a_n)_{n \in \m…

math.CO2023★ 2 cited

Sparse graph counting and Kelley-Meka bounds for binary systems

Yuval Filmus, Hamed Hatami, Kaave Hosseini +1

In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In thi…

math.CO2023

Generalized polymorphisms

Gilad Chase, Yuval Filmus

We find all functions $f_{0}, f_{1}, \dots, f_{m} : {0, 1}^{n} \to {0, 1}$ and $g_{0}, g_{1}, \dots, g_{n} : {0, 1}^{m} \to {0, 1}$ satisfying the following identity for all $n \times m$ mat…

math.CO2023★ 1 cited

MC-finiteness of restricted set partition functions

Yuval Filmus, Eldar Fischer, Johann A. Makowsky +1

A sequence $s (n)$ of integers is MC-finite if for every $m \in N^{+}$ the sequence $s^{m} (n) = s (n) mod m$ is ultimately periodic. We discuss various ways of proving and di…

math.CO2022★ 5 cited

Irreducible subcube partitions

Yuval Filmus, Edward Hirsch, Sascha Kurz +4

A \emph{subcube partition} is a partition of the Boolean cube ${0, 1}^{n}$ into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are…

math.CO2022★ 6 cited

Affine vector space partitions

John Bamberg, Yuval Filmus, Ferdinand Ihringer +1

An affine vector space partition of $AG (n, q)$ is a set of proper affine subspaces that partitions the set of points. Here we determine minimum sizes and enumerate eq…

math.CO2022

Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings

Gilad Chase, Neta Dafni, Yuval Filmus +1

We give a characterization of the largest $2$ -intersecting families of permutations of ${1, 2, \dots, n}$ and of perfect matchings of the complete graph $K_{2 n}$ for all $n \geq 2$ …

math.CO2022★ 1 cited

Junta threshold for low degree Boolean functions on the slice

Yuval Filmus

We show that a Boolean degree $d$ function on the slice $(k [ n ])$ is a junta if $k \geq 2 d$ , and that this bound is sharp. We prove a similar result for $A$ -valued degree $d…

math.CO2022

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems

Yuval Filmus, Nathan Lindzey

We give simpler algebraic proofs of uniqueness for several Erdős-Ko-Rado results, i.e., that the canonically intersecting families are the only largest intersecting families. Using…

math.CO2021★ 1 cited

Boolean functions on $S_{n}$ which are nearly linear

Yuval Filmus

We show that if $f : S_{n} \to {0, 1}$ is $ε$ -close to linear in $L_{2}$ and $E [f] \leq 1/2$ then $f$ is $O (ε)$ -close to a union of "mostly disjoint" cosets, and moreover…

math.CO2019

High dimensional Hoffman bound and applications in extremal combinatorics

Yuval Filmus, Konstantin Golubev, Noam Lifshitz

One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of…

math.CO2018★ 2 cited

FKN theorem for the multislice, with applications

Yuval Filmus

The Friedgut-Kalai-Naor (FKN) theorem states that if $f$ is a Boolean function on the Boolean cube which is close to degree 1, then $f$ is close to a dictator, a function depending…

math.CO2018

A Sauer-Shelah-Perles Lemma for Lattices

Stijn Cambie, Bogdan Chornomaz, Zeev Dvir +2

We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $…

math.CO2018

Boolean constant degree functions on the slice are juntas

Yuval Filmus, Ferdinand Ihringer

We show that a Boolean degree $d$ function on the slice $(k [ n ]) = {(x_{1}, \dots, x_{n}) \in {0, 1} : \sum_{i = 1}^{n} x_{i} = k}$ is a junta, assuming that $k, n - k$ are large eno…

math.CO2018

Boolean degree 1 functions on some classical association schemes

Yuval Filmus, Ferdinand Ihringer

We investigate Boolean degree 1 functions for several classical association schemes, including Johnson graphs, Grassmann graphs, graphs from polar spaces, and bilinear forms graphs…

math.CO2017★ 5 cited

A comment on Intersecting Families of Permutations

Yuval Filmus

Ellis, Friedgut and Pilpel proved that for large enough $n$ , a $t$ -intersecting family of permutations contains at most $(n - t)!$ permutations. Their main theorem also states that e…

math.CO2017

On the Bhattacharya-Mesner rank of third order hypermatrices

Edinah K. Gnang, Yuval Filmus

We introduce the Bhattacharya-Mesner rank of third order hypermatrices as a relaxation to the tensor rank and devise from it some bounds for the tensor rank. We use the Bhattachary…

math.CO2016★ 3 cited

Ahlswede-Khachatrian Theorems: Weighted, Infinite, and Hamming

Yuval Filmus

The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a $k$ -uniform $t$ -intersecting family on $n$ points, and describes all optima…

Chvátal's conjecture: a proof from The Book

Triviality of promise polymorphisms

Boolean degree one functions on the Grassmann scheme

Approximate polymorphisms of predicates

Sensitivity and Hamming graphs

Aggregation of evaluations without unanimity

Effective MC-finiteness

Sparse graph counting and Kelley-Meka bounds for binary systems

Generalized polymorphisms

MC-finiteness of restricted set partition functions

Irreducible subcube partitions

Affine vector space partitions

Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings

Junta threshold for low degree Boolean functions on the slice

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems

Boolean functions on Sn​ which are nearly linear

High dimensional Hoffman bound and applications in extremal combinatorics

FKN theorem for the multislice, with applications

A Sauer-Shelah-Perles Lemma for Lattices

Boolean constant degree functions on the slice are juntas

Boolean degree 1 functions on some classical association schemes

A comment on Intersecting Families of Permutations

On the Bhattacharya-Mesner rank of third order hypermatrices

Ahlswede-Khachatrian Theorems: Weighted, Infinite, and Hamming

Boolean functions on $S_{n}$ which are nearly linear