Majority coloring of a digraph is a coloring of its vertices such that for each vertex v, at least half of the out-neighbors of v have different colors than v. A digraph D is majority k–choosable if for any assignment of lists of colors of size k to the vertices there is a majority coloring of D from these lists. We present an algorithm that generates a majority coloring of arbitrary digraph from lists of size 4. In fact, our method solves a more general problem, where the fraction of out-neighbors having same color may be different for every vertex (in particular, not necessarily equal to 1/2). In addition, we also prove some results on the majority colorings of infinite digraphs.

Keywords: majority coloring, unfriendly partition, majority k-choosability, digraph, infinite digraph.
AMS Subject Classification: 05C15, 05C20, 05C63.

The container method proved to be applicable in several areas of combinatorics. In this talk, I talk about some new applications in discrete geometry; one of them is about a minimum size of an epsilon-net in a point-line system in the plane.

It is joint work with Jozsef Solymosi.

The classical one-dimensional bin packing problem is among the most frequently studied combinatorial optimization problems. It is well-known that finding an optimal packing is NP-hard. Consequently, a large number of papers have been published which look for polynomial time algorithms that find feasible solutions with an acceptable approximation quality. One class of the algorithms is the so called on-line algorithms. An on-line algorithm packs the elements in order of their arrival, without knowing the subsequent elements.

In this talk we overview some results from the above areas with some practical application possibilities.

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k≥2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.

In recent years nanostructures are gaining importance and its use in various areas starting from a pharmaceutical use. An important break through represents method of folding a single strand DNA into a 3D shape. Rothemund [3] showed how to do this by specifying solely nucleotide sequence of the DNA in such a way that a given region of a strand binds to exactly one other region in the same strand. Technologically it would be easier to construct such structures not from DNA but from polypeptides consisting of amino acids. In 2015 Potapov et al. [2] showed that this is possible using so called coiled coil (CC) peptides. Later Gradišar et al. [1] presented graph theoretical results about classes of graphs permitting such a construction using a single strand CC peptide or DNA.

The crucial building block of the construction is an orthogonal base of CC peptides. Roughly speaking, the orthogonal base consists of CC peptides, where each peptide interacts with exactly one other peptide. Would we be dealing with nucleotides and DNA, a well known set {A, C, G, T} represents such an orthogonal base of size 4. The elements of the base are then glued together into a single strand chain used to construct polypeptide origami 3D nano structures. The individual elements are chemically sequences of 7 amino acids called heptads.

In this paper we show that given a set of CC heptads to choose the largest subset of them that represents an orthogonal base is an NP-complete problem. Furthermore, we give an exact algorithm to construct such a set, that is currently experimentally being verified. Finally, we extend our results to a multiheptad set of CC peptides and give a meta-heuristic algorithm that gives 3-10 times larger orthogonal base than our exact method using single heptad CC peptides.

Some results of this work Silađi presented in his thesis [4].
The authors acknowledge a partial support from the project (Graph Optimisation and Big Data, N2-0053) and research core funding No. P2-0359 financially supported by the Slovenian Research Agency.

[1] Helena Gradišar, Sabina Bozic, Tibor Doles, Damjan Vengust, Iva Hafner-Bratkovic, Alenka Mertelj, Ben Webb, Andrej Sali, Sandi Klavzar, and Roman Jerala. Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments. Nature chemical biology, 9(6):362– 366, 2013.
[2] Vladimir Potapov, Jenifer B Kaplan, and Amy E Keating. Data-driven prediction and design of bZIP coiled-coil interactions. PLoS Comput Biol, 11(2):e1004046, 2015.
[3] Paul WK Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297–302, 2006.
[4] Daniel Silađi. Computational methods for polypeptide origami design. BSc thesis, University of Primorska, Faculty of Mathematics, Natural Science and Information Technologies, 2017.

When a firm faces an uncertain demand, it is common to procure supply using some type of option in addition to spot purchases. A typical problem of this type involves capacity being purchased in advance, with a separate paymentmade that applies only to the part of the capacity that is needed. We consider a discrete version of this problem in which competing suppliers choose a reservation price and an execution price for blocks of capacity, and the buyer, facing known distributions of demand and spot price, needs to decide which blocks to reserve. We show how to solve the buyer's combinatorial problem efficiently and prove that suppliers can do no better than offer blocks at execution prices that match their costs, making profits only from the reservation part of their bids. Finally, we show that in an equilibriumthe buyer selects the welfare maximizing set of blocks.

Joint work with Edward Anderson (University of Sydney, Australia) and Lusheng Shao (University of Melbourne, Australia)

Let H and G be simple graphs on n vertices, where n is sufficiently large. Define the Ore-degree of an edge as the sum of the degrees of its endpoints. Then we define the Ore-degree of H as the maximum of the Ore-degrees taken on the edges of H. We prove that if H has Ore-degree at most 5 and G has minimum degree at least 2n/3 then H is a spanning subgraph of G.

In Hungary hundreds of thousands of cows produce milk for us. A common disease of them is the mastitis that influences substantially their productivity and profitability. The usual practice is to decide on a rule of thumb basis whether the ill cow should be kept or sold. E.g. they are kept till the fifth mastitis event occurs. The present study investigates this problem from a mathematical modelling point of view. The relative amount of the possible lost profit is in the order of magnitude of 10s of percentages, which is quite large, especially regarding the profitability outlooks of the dairy industry¹.

The problem lies in the personal relationship of the farmers to the cows, and in the complexity of the estimation of the uncertain future scenarios. We present a model that is based on collected historical data on the distribution of several model parameters such as the length of the illness, the amount of medicine needed, number of inseminations for conception etc. The applied methodology is the microsimulation (i.e. we simulate all possible event one-by-one) and stochastic optimization. Our typical result is a suggested decision on the basis of the expected value of the profit/loss for the given animal¹.

The simple program that is capable to solve such problems with simple input data is available for smart phones and tablet (having Android 6.0 or newer operating systems) at www.inf.u-szeged.hu/~banhelyi/Buu

In the conference talk we shall report on the first results that confirm our research expectations in terms of improvement of the business decision. The ongoing research will focus on the recommendation system type data mining technology that can utilize the local specialties of the dairy farm in question, and to validate the additional advantage involved in it.

Reference
[1] Economic modelling of the transition from a travel times based to a travel time based ticket system. Research Report for the Szeged Transportation Inc., in Hungarian (Az utazásszám alapú jegyrendszer időalapú jegyrendszerré történő átállításának gazdasági modellezése), KNRet, Szeged, 2010.

In bin packing with cardinality constraints (BPCC), there is an upper bound k on the number of items that can be packed into each bin, additionally to the standard constraint on the total size of items packed into a bin. We study the algorithm First Fit, that acts on a list of items, packing each item into the minimum indexed bin that contains at most k-1 items and has sufficient space for the item.

An upper bound, namely 2.7-2.4/k for the asymptotic approximation ratio of FF was known from 1975. Now we give the tight bound for any specific value of k.

This is as follows: 5/2- 2/k for k is between 2 and 4; 8/3-8/(3k) if k is between 4 and 10, and 2.7-3/k if k is at least 10 (where the values 4 and 10 are included in two cases each). For the tightness proof we use different weighting functions for the different cases.

Joint work with Leah Epstein.

In a digraph we want to find K spanning arborescences such the most used edge belongs to a minimum number of arborescences, subject to this, the second most used edge belongs to a minimum number of arborescences, and so on. For short, we are interested in a decreasingly-minimal packing of K arborescences. In an analogous problem, we look for a decreasingly-minimal strongly connected orientation of a graph, that is, the largest in-degree of a node should be as small as possible, subject to this, the second largest in-degree should be as small as possible, and so on.

Similar questions can be posed concerning many other known combinatorial optimization problems such as packing st-paths of a digraph or bases of a matroid. In the literature, this kind of problems are sometimes called ”egalitarian” or ”shifted” or ”fair” optimization. When K is small, a straightforward parallel edge- multiplicating technique reduces the problem to the minimum cost version of the basic problem. However, for large K this approach is hopeless to get a polynomial algorithm. In this talk, we develop a strongly polynomial algorithm, for network flows and polymatroid intersections.

The talk is based on a joint work with Kazuo Murota.

Scientific conferences have become an essential part of academic research and require significant investments (e.g. time and money) from their participants. It falls upon the organizers to develop a schedule that allows the participants to attend the talks of their interest. We present a combined approach of assigning talks to rooms and time slots, grouping talks into sessions, and deciding on an optimal itinerary for each participant. Our goal is to maximize attendance, taking into account the common practice of session hopping. On a secondary level, we accommodate presenters' availabilities. We use a hierarchical optimization approach, sequentially solving integer programming models, which has been applied to construct the schedule of the MathSport International (2013), MAPSP (2015) and ORBEL (2017) conferences.

The problem considers a synchronized tactical planning of sales territories and corresponding delivery routes for 3PL /4PL providers. Such a planning is challenging in FCMG markets where Traditonal Trade is still strong compared to Key Accounts. In such markets, 3PL/4PL providers have exclusive distribution agreements with several brands. As the rule of thumb, each brand insists on a sales-force that sells only its products. On the other hand, the delivery of products from different brands can be consolidated. The brands are compatible if such consolidation is possible. The lists of the shops of two compatible brands usually overlap to a great extent.

The planner of sales territories for a single brand usually has complete freedom to organize territories for his/her sales-force. A single salesperson thus gets a territory that is often splitinto sub-territories, where each sub-territory can be handled during a single working day. Goods that are sold during a working day are either delivered during the next 24 hours, or the next 48 hours. All sub-territories of the sales-force related to a particular brand and assigned to a particular day can be identified with the daily list of shops in them. Based on the daily lists of shops from all its brands, 3PL/4PL provider plans its delivery routes. Since the planning of sales for different brands is not synchronized, it results in more visits and consequently in more kilometers and more vehicles engaged.

We model the problem and propose an algorithm. We also present some computational results for real world instances.

The terminal-pairability problem has been introduced by L. Csaba, R.J. Faudree, A. Gyárfás, J. Lehel, and R.H. Schelp in 1992. It asks the following question: given a simple base graph G and a list of pairs of vertices of G (which list may contain multiple copies of the same pair), can we assign to each pair a path in G whose end-vertices are the two elements of the pair, such that the set of chosen paths are pairwise edge-disjoint.

In this lecture, we investigate the terminal-pairibility problem in the case when the base graph is complete, complete bipartite, or a grid graph. If we have some bounds on the demand graph (maximum degree, edge number) then the terminal pairability problem is solvable. We improve these bounds (maximum degree) or prove the best possible ones (edge number) in several cases. The lecture is based on four papers joint with (some of) L. Colucci, P.L. Erdős, T. Mezei, and G. Mészáros.

The semi-random method was introduced in the early eighties. In its first form of the method lower bounds were given for the size of the largest independent set in hypergraphs with certain uncrowdedness properties. The first geometrical application was a major achievement in the history of Heilbronn's triangle problem. It proved that the original conjecture of Heilbronn was false. The semi-random method was extended and applied to other problems. In this paper we give two further geometrical applications of it.

First, we give a slight improvement on Payne and Wood's upper bounds on a Ramsey-type parameter, introduced by Gowers. We prove that any planar point set of size

Ω(	n2log n	)
	log log n

contains n points on a line or n independent points.

Second, we give a slight improvement on Schmidt's bound on Heilbronn's quadrangle problem. We prove that there exists a point set of size $n$ in the unit square that doesn't contain four points with convex hull of area

O(n^-3/2(log n)^1/2).

Joint work with Endre Szemerédi.

Today resource scheduling problems are in the spotlight of operations research, as these problems have several applications in real life as well. These problems can be considered as assignment problems with additional requirements. Application areas cover the scheduling of pilots and stewardess to designated flights, shop assistants to shifts and public transport (vehicles) to routes, and many more similar type of problems. The additional requirements are greatly dependent on the application, blemishing the flow network behaviour of the problem, hence the characterisation of these problems can only be achieved by integer programming, usually leading to an NP-hard problem. Therefore the solution of these optimization models in practice is a real professional challenge.

Our talk focuses on scheduling bus drivers for different lines of the public transport network of Budapest. Although the actual transport routes and timetables are rarely modified, it is essential to constantly develop improved schedules, which is still surprisingly done in Excel for the Budapest Transportation Company. On the one hand this practise from the company side requires a huge amount of time and human resources. On the other hand the quality of the solution is either not guaranteed or not known. (Usually, both is true.)

In our approach, the initial step was to build the basic integer linear programming (ILP) model that includes all constraints possed by the client. The obtained ILP model falls into the NP-hard problem class. Since there is no polynomial algorithm for such problems, the main aim was to develop a model variant that can be solved by available software effciently giving an acceptable result for even larger problem instances within a reasonable time frame.

We show that using a combination of an aggregate model and a more detailed one, we could effciently get such solutions that are usually better quality of that one produced by the expert of the transportation company and in most of the cases the result could be obtained using much less time. In our approach we are not following the frequently used column generation technique based on drivers feasible rosters.

The work was carried out in collaboration with T-Systems Hungary Ltd.

A set of integers is, informally, called heapable if its elements can be inserted into a binary tree (not necessarily complete) that respects the heap property. The definition naturally extends to partial orders.

We investigate the partitioning of partial orders into a minimal number of heapable subsets. We prove a characterization result reminiscent of the proof of Dilworth's theorem, which yields as a byproduct a flow-based algorithm for computing such a minimal decomposition. On the other hand,

• for interval partial orders a longest heapable subsequence can be computed in polynomial time.
• for trapezoid partial orders we prove that a minimal decomposition can be computed by a simple greedy-type algorithm.

The talk will also discuss a couple of open problems related to the analog of the Ulam-Hammersley problem for decompositions of sets and sequences of elements of a partial order into heapable subsets.

Introduce the notation [n] = {1, 2, . . . , n}, then the family of all k-element subsets of [n] can be denoted as ([n]k ). Suppose that ℱ ⊂ ([n]k ). Then its 𝓁-shadow σ_𝓁(ℱ) is the family of all k − 𝓁-element sets obtained by deleting 𝓁 elements from the members of ℱ, that is σ(ℱ) = {A : |A| = k − 𝓁, there is an F ∈ ℱ such that A ⊂ F}. The shadow theorem determines max |σ_𝓁(ℱ)| for fixed n, k and |ℱ|. We will survey variants of the shadow theorem. One of them (proved by the author in 1964) determines the minimum of the ratio |σ_𝓁(ℱ)|/|ℱ| for fixed n and k. The main goal of the present talk is to exhibit a new improvement of this result for the case when |ℱ| is large.

In recent years the field of text mining has witnessed an exponential growth due to rapid technological development and ubiquitous information technology. When discovering useful information from natural languages, classification algorithms are combined with the analysis of lexicographic and linguistic patterns. The main objective of the paper/talk is to briefly present the field of text mining including all relevant methodologies and techniques. Moreover, we developed and evaluated various predictive models based on the case study of the Slovenian Tourist Corpus which encompasses the learning set of 4.688 texts. These texts have been previously classified in one of the 27 classes by an expert. We compared the performance of different machine learning algorithms for classification on the original and lemmatized texts that were properly pre-processed before the modelling process. We examined the effect of eliminating stop words and those without any information gain on the final model accuracy. Open source software WEKA was used, which includes a wide collection of techniques and algorithms for the construction and evaluation of predictive models. The final evaluation confirms the minimal impact of the factors that were expected to affect the accuracy of the predictive models.

We consider parallel machine scheduling with job assignment restrictions, i.e., each job can only be processed on a certain subset of the machines. Moreover, each job requires a set of renewable resources. Any resource can be used by only one job at any time. The objective is to minimize the makespan. We present approximation algorithms with constant worst-case bound in the case that each job requires only a fixed number of resources. For some special cases optimal algorithms with polynomial running time are given. If any job requires at most one resource and the number of machines is fixed, we give a PTAS. On the other hand we prove that the problem is \APX-hard, even when there are just three machines and the input is restricted to unit-time jobs.

(joint work with Gyorgy Dosa and Zsolt Tuza)

In the talk I give an overview of the published results on the subject in the title, and then I present new, yet unpublished results on machine scheduling problems with additional non-renewable resources and the total weighted completion time objective. I will discuss complexity and approximability results, and we will also see that well-known scheduling rules prove once more useful in a new context.

This is a joint work with Péter Györgyi

Mesh partitioning is an indispensable tool for efficient parallel numerical simulations. Its goal is to achieve load balance while minimizing communication between the processes of the simulation. While established graph-based partitioning tools yield a high solution quality, their scalability is limited. Geometric approaches usually scale better, but their solution quality is comparably poor for non-trivial mesh topologies.

We present a scalable version of k-means that is also adapted to yield balanced clusters. We combine this balanced k-means with space-filling curves for bootstrapping and graph-based local refinement for quality-oriented postprocessing in our new partitioning algorithm Geographer. With this combination, we address the previous limitation of scalability and solution quality.

Our experiments with up to 16384 MPI processes on established benchmark meshes show that the following:
(i) Geographer's quality is in most cases better than the quality of geometric ParMETIS, graph-based ParMETIS, and ParHIP, the parallel version of KaHIP;
(ii) Geographer scales well on large inputs and is faster than geometric ParMETIS when using at least 4096 processes;
(iii) a Delaunay mesh with a few billion vertices and edges can be partitioned in about ten seconds with balanced k-means and in half a minute with complete Geographer.

Pokrovskiy and, independently, Alon, Huang and Sudakov introduced the MMS (Manickam-Miklós-Singhi) property of hypergraphs: "for every assignment of weights to its vertices with nonnegative overall sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H". This leads to the definition of the following hypergraph parameter: The vertex sign balance of a hypergraph is the minimum number of edges whose total weight is nonnegative, where the minimum is taken over all assignments of weights to the vertices with nonnegative overall sum.

WThe vertex sign balance is always between 0 and the minimum degree of the graph or hypergraph, both bounds being sharp. General and special properties (for graphs or hypergraphs) of this parameter will be presented. I particular,it will be shown that this parameter measures the "matchingability" of graphs and similar observation can be made for hypergraphs. This characterization of the vertex sign balance of the graphs leads to the result that the question if a graph or hypergraph has the MMS property is NP-complete.

The dual of the vertex sign balance, the edge sign balance is defined by the minimum number of vertices whose total weight is nonnegative, where the minimum is taken over all assigments of weights to the edges with nonnegative overall sum and the weight of a vertex is obtained as the sum of the weights of the edges containing the vertex. For graphs this parameter is always between 1 and 2, being two iff the graph is bipartite. However, for 3-uniform graphs, while being three-partite would yield the edge sign balance being three, the opposite is most probably not true. The edge sign balance can be a "measure" for "coverability", more accessible than three- (or multi-) partitness.

Let D = {d_1,1, d_1,2, . . . , d_1,n}, {d_2,1, d_2,2, . . . , d_2,m} be a degree sequence of a bipartite graph. The swap Markov chain takes two random edges, (v₁, u₁),(v₂, u₂), of a relization G of D, removes it and adds edges (v₁, u₂) and (v₂, u₁) if none of them are presented in G. It is well known that such a Markov chain is irreducible on the realizations of D. The conjecture is that it is rapidly mixing, however, the rapid mixing has been proved only for very limited degree sequences so far. Here we prove the following theorem.

Let 0 ≤ c₁ ≤ c₂ ≤ |U| = n and 0 ≤ d₁ ≤ d₂ ≤ |V | = m be integer parameters and assume that D satisfies the following properties:

c₁ ≤ d(v) ≤ c₂, ∀v ∈ V
d₁ ≤ d(u) ≤ d₂, ∀u ∈ U.

Furthermore, assume that c₂ ≤ c₁ + 1 or d₂ ≤ d₁ + 1 or

(c₂ − c₁ − 1) · (d₂ − d₁ − 1) < 1 + max {c₁(m − d₂), d₁(n − c₂)}

holds. Then the swap Markov chain on the realizations of this bipartite degree sequence is rapidly mixing.

The prescribed conditions allow to prove rapid mixing for a much wider class of degree sequences. For example, our theorem covers the case when n = m, and all degrees are between 1/3 n and 2/3 n, inclusive.

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems - that are in general NP-hard - efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; and (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We propose a general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. Thus, one main contribution of this work is to propose novel features for tree decompositions. Moreover, we report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.

Based on joint work with Michael Abseher and Stefan Woltran

Watson-Crick automata are inspired from the Nature, as instead of a normal tape, a Watson-Crick tape, i.e., a DNA molecule is considered as input. A DNA molecule has two strands, subsequently Watson-Crick automata have two reading heads, one for each strand. DNA strands have orientation, the 5'->3' direction is preferred in some biochemical reactions. In 5'->3' Watson-Crick automata the two reading heads start from the two extremes of the input (the opposite ends of the molecule) and finish the process when the heads meet. With 5'->3' Watson-Crick finite automata the class of linear context-free languages can be accepted, and some of its subclasses by some restricted variants. Extending these automata with a pushdown stack, a new mildly context-sensitive family of languages can be accepted containing all the context-free languages, and the linguistically important three non context-free languages. Variants of this model will also be shown.

We discuss and survey some recent developments concerning the application of concepts of parameterized algorithmics to polynomial-time solvable problems. Example problems include Matching, Triangle Detection and Enumeration, and Graph Hyperbolicity.

The Incremental Knapsack Problem (IKP) is a natural extension of the classical 0-1 Knapsack Problem with a time perspective. In particular, the knapsack capacity increases over the time periods and thus allows more items to be packed. However, if an item is placed in the knapsack in a certain period, then it cannot be removed again in later periods. The objective function maximizes the sum of the profits over all time periods.

In our contribution we first prove the tightness of the approximation ratio of a general purpose algorithm for incremental problems. Then we devise a Polynomial Time Approximation Scheme (PTAS) when the number of time periods is constant. Under the mild and natural assumption that each item can be packed in the first time period, we analyze different natural approximation algorithms. We also give a more involved analysis based on Linear Programming techniques providing better approximation ratios for the special cases of two and threetime periods.

Joint work with Federico Della Croce and Rosario Scatamacchia (Politecnico di Torino)

We consider the problem of designing an road network in a forest with the goal of providing access to tree harvest locations. The environment is modelled as a node induced grid graph, with each node (cell) containing properties of the respective area. A number of objectives can be considered when designing road networks: topology, environmental restrictions, access to specific areas and soil properties. Current solution in forest access road design focus on finding optimal routes to pre-specified locations with the goal of minimising distance. These are often modelled using Steiner trees. Although Steiner trees provide a theoretical optimum solution, they are both hard to find, and not practical in larger areas. In practice, access road networks are often end up as sets of loops, to improve traffic and avoid congestion. We propose a new model using cactus-like graph structures. Our goal is to find a minimum cost cactus-like subgraph, subject to a prize limit (amount of accessed harvestable sites). We propose hybrid heuristic methods to solve the problem.

An r-matrix is a matrix with symbols in {0,1,...,r-1}. A matrix is simple if it has no repeated columns. Let the support of a matrix F, supp(F) be the largest simple matrix such that every column of supp(F) is in F. For a family of r-matrices ℱ, we define forb(m,r,ℱ) as the maximum number of columns of an m-rowed, r-matrix A such that F is not a row-column permutation of A for all F ∈ ℱ. While many results exist for r=2, there are fewer for larger numbers of symbols. We expand on the field of forbidding matrices with r-symbols, introducing a new construction for lower bounds of the growth of forb(m,r,ℱ) (with respect to m) that is applicable to matrices that are either not simple or have a constant row. We also introduce a new upper bound that helps with avoiding non-simple matrices, limited either by the asymptotic bounds of the support, or the size of the forbidden matrix, whichever is larger. We represent the well-known technique of standard induction as a graph, and use graph theory methods to obtain asymptotic upper bounds. With these techniques we solve multiple, previously unknown, asymptotic bounds for a variety of matrices. Finally, we end with block matrices, or matrices with only constant row, and give bounds for all possible cases.

An extremal graph problem has its universe, 𝕌, e.g., simple graphs, multigraphs, digraphs, hypergraphs, multihypergraphs, and we fix a family ℒ of some “excluded substructures” and try to maximize some parameter e = e(G) under some conditions on G. Here e may be the number of edges, hyperedges, or the number of some substructures H ⊂ G,...

Algorithmic approach has influenced very much the development of Discrete Mathematics. In large part of extremal graph theory the extremal strutures are either very simple, or at least they can be approximated be some very simple structures. (In some other cases they have extremely complicated structure.) One of the basic questions is that if there exist almost extremal structures of fairly simple structures, can they be found in a bounded number of steps, independently of n.

These and related question will be discussed.

In the talk we describe how approximate numerical solutions of a suitable initial value problem of a system of ordinary differential equations can be used to establish rigorous lower and upper estimate for the clique number of a given graph.

In order to assess the practical utility of the proposed approach we have carried out numerical experiments. We outline the benchmark instances used in the computations and also present tables summarising the results.

The inmate assignment project, in close collaboration with the PA Dept. of Corrections, took five years from start to successful implementation. Our novel Inmate Assignment Decision Support System (IADSS) is designed with the main goal of simultaneously, and system-wide optimally, assigning the inmates to the correctional institutions. IADSS includes a new hierarchical multi-objective MILO model, which accurately describes the inmate assignment problem. This is the first time that OR methodologies have been used to optimize the operations, and built into the routine business practice, of a correctional system, thus it opens a rich and untouched area for the application of OR.

Betweenness centrality of a vertex measures the fraction of shortest paths going through that vertex. This is a popular quantity for evaluating the importance of a vertex in a large network. The k-bounded version considers only shortest paths of length at most k. The k-bounded betweenness centralities of a vertex for varying k form the profile of the vertex. The profile expresses the importance of the vertex in different scales of locality.

We consider profiles in trees, and give results on their behavior in the worst case, and in scale-free random trees.

Joint work with Ben Fish and Rahul Kushwaha.

We say that a subgraph H of a graph G is singular if either all vertices of H have equal degree in G or they have mutually distinct degrees. Given a fixed graph F, the singular Ramsey number Rs(F) is the smallest integer n such that in every 2-coloring of the edges of any complete graph of order at least n the graph of color-1 edges or that of color-2 edges contains a singular subgraph isomorphic to F. We present general bounds and tight results, one of which states Rs(K_3) = 22.

This is joint work with Yair Caro.